package subject_set.offer100;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author haomin
 * @date 2022/10/27 18:02
 **/
public class Offer59_Ⅱ {
    class MaxQueue {
        Deque<Integer> q1;
        Deque<Integer> q2;
        public MaxQueue() {
            q1 = new LinkedList<>();
            q2 = new LinkedList<>();
        }

        public int max_value() {
            return q2.isEmpty() ? -1 : q2.peek();
        }

        public void push_back(int value) {
            q1.offer(value);
            while(!q2.isEmpty() && q2.peekLast() < value) q2.pollLast();
            q2.offer(value);
        }

        public int pop_front() {
            if(q1.isEmpty()) return -1;
            int value = q1.poll();
            if(q2.peek() == value) q2.poll();
            return value;
        }
    }
}